// ++++++++++++++++++++++++++++++++++++++++
// 《零基础Go语言算法实战》源码
// ++++++++++++++++++++++++++++++++++++++++
// Author:廖显东（ShirDon）
// Blog:https://www.shirdon.com/
// Gitee:https://gitee.com/shirdonl/goAlgorithms.git
// Buy link :https://item.jd.com/14101229.html
// ++++++++++++++++++++++++++++++++++++++++

package main

import "fmt"

// 接受数组并返回排序数组
func fibonacciSearch(arr []int) []int {
	if len(arr) < 2 {
		return arr
	}

	//创建一个足以覆盖数组长度的斐波那契数列
	fibM2, fibM1, fibM := 0, 1, 1
	for fibM < len(arr) {
		fibM2, fibM1 = fibM1, fibM
		fibM = fibM1 + fibM2
	}

	//使用斐波那契数列作为指南对数组执行二进制搜索
	offset := -1
	for fibM2 > 1 {
		i := min(offset+fibM2-fibM1, len(arr)-1)

		if i > 0 && arr[i] < arr[offset+fibM2-fibM1+1] {
			fibM2, fibM1 = fibM1, fibM2-fibM1
			offset = i
		} else {
			fibM2, fibM1 = fibM2-fibM1, fibM1
		}
	}

	//使用插入排序对数组进行排序
	for i := offset + 1; i < len(arr); i++ {
		tmp := arr[i]
		j := i - 1
		for j >= 0 && arr[j] > tmp {
			arr[j+1] = arr[j]
			j--
		}
		arr[j+1] = tmp
	}

	return arr
}

// 用于查找两个整数之间的最小值的辅助函数
func min(x, y int) int {
	if x < y {
		return x
	}
	return y
}

func main() {
	arr := []int{66, 8, 88, 55, 5, 28}
	sortedArr := fibonacciSearch(arr)
	fmt.Println(sortedArr)
}

//$ go run fibonacciSearch.go
//[5 8 28 55 66 88]
